package com.ljy.my_study.动态规划.最长递增子序列;

import java.util.Scanner;

/** 
* @author James
* @date 2018年6月15日 
*/
public class TestMain {
	/**
	 * （1）随机生成一个有10个元素的数组，然后输出它的最长递增子序列 
（2）输出以其中某一个元素为结尾的最长递增子序列的长度
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] L = new int[n];
        for (int j = 0; j < n; j++)
            L[j] = in.nextInt();
        double[] B = new double[n + 1];
        B[0] = Integer.MIN_VALUE;
        B[1] = L[0];
        int Len = 1;
        int p, r, m;
        for (int i = 1; i < n; i++) {
            p = 0;
            r = Len;
            while (p <= r) {
                m = (p + r) / 2;
                if (B[m] < L[i])
                    p = m + 1;
                else
                    r = m - 1;
            }
            B[p] = L[i];
            if (p > Len)
                Len++;
        }
        System.out.println(Len);
	}
}
